Use of Low Earth Orbit (LEO) satellite networks is a promising approach for global data communications (including broadband) in view of their low delay and bit error characteristics compared to Geostationary (GEO) satellites. Further, they do not require high power antennas in ground terminals due to their low distance from the ground. However, due to their orbit, the communication link between a ground terminal and an LEO satellite will be available periodically only for a few minutes. In order to provide continuous communication between ground terminals, the LEO satellites need to be interconnected via inter-satellite links (called crosslinks) and terminal-terminal data traffic will be routed over multiple satellites using these crosslinks. Typically, an LEO satellite network consists of multiple orbit planes, and each plane consists of multiple satellites. The satellite topology (neighbor relationship) within a plane remains invariant while inter-plane topology will change constantly; interplane crosslinks will be dynamically set up and removed. Terminal-satellite associations (uplink and downlink connectivity) will also be changing constantly. Traffic routing in such a dynamically changing network considering the bandwidth and priority requirements of user traffic, network failures, and network congestion is a complex problem.
Several proposals have been made for distributed routing in LEO satellite networks; i.e., each payload router determines routing decisions independently for each packet.
E. Ekici, I. F. Akyildiz, M. D. Bender, A Distributed Routing Algorithm for Datagram Traffic in LEO Satellite Networks, IEEE/ACM Transactions on Networking, VOL. 9, NO. 2, April 2001 propose a distributed routing algorithm for routing datagram traffic in an LEO satellite network. The algorithm generates minimum propagation delay paths. The algorithm is based on the concept that the entire earth is covered by logical locations of satellites. These logical locations do not move and are filled by the nearest satellite. This concept is similar to the grid concept in the present invention. In Ekici et al routing is performed by considering these logical locations as hops. Unlike classical routing algorithms used in terrestrial routers, the algorithm does not require satellites to exchange topology information, but computes routes based on some mathematical properties of minimum delay paths between logical locations taking into account the different distances between neighbor locations in polar region and non-polar regions. Based on the mathematical properties, a routing table is generated at design time that prescribes on which direction (up, down, right, or left) a satellite should route a packet depending on which region the destination is in (polar or non-polar). The table also includes a secondary direction that should be used if the link on the primary direction is congested, i.e., the output queue is longer than some threshold. Thus, the routing algorithm is capable of rerouting packets around congestion and failure points with low degradation in performance. This routing algorithm is intended for pure datagram traffic. It does not consider bandwidth (QoS) and priority of traffic.
Ekici et al., have extended this algorithm to multicast routing in E. Ekici, I. F. Akyildiz, M. D. Bender, A Multicast Routing Algorithm for LEO Satellite IP Networks, IEEE/ACM Transactions on Networking, VOL. 10, NO. 2, April 2002. The multicast extension requires routing information exchange between payloads.
Vijay Kapoor, Directional Routing of Packets in a Satellite Network, U.S. Pat. No. 6,404,769, issued Jun. 11, 2002 proposes a method for routing packets across a satellite constellation that is made up of multiple orbital planes, each plane carrying multiple satellites that are equally spaced in the plane. Satellites in the same orbital plane are connected via north-south crosslinks. Satellites in different orbital planes are connected via east-west crosslinks. When a connection is needed between two satellites that are in different planes, a controller station in the ground determines a route for the connection taking into account the traffic load on various crosslinks. That is, the cost for route optimality is traffic load on the path rather than delay. The route so determined consists of a “band” which denotes a logical region in the constellation that is orthogonal to orbital planes. The controller provides this route information including the band information, the destination plane, and the destination satellite id to the source satellite which includes it in all packets belonging to that connection. Thus, this scheme employs source routing. Satellites forward packets using this route information by forwarding packets on the source plane until the specified band is reached, then on the band towards the destination plane, and finally on the destination plane towards the destination satellite. In this method, the satellites do not have any route adaptation capabilities. All rerouting decisions are made only by the controller on the ground. Another limitation of this scheme is that it does not consider traffic priority and does not support preemption. Also, the “band” based routes are unlikely to be optimal, since they constrain shortest path selection.
V. V. Gounder, R. Prakash, H. Abu-Amara, Routing in LEO-Based Satellite Networks, IEEE Symposium on Wireless Communications and Systems, April 1999 propose a virtual connection-oriented approach based on tag switching to route data in an LEO satellite network. Routing tables are computed by ground stations and uploaded to satellites at predetermined intervals. Routes are computed by ground stations for different network snapshots. Only forwarding tables for a limited set of snapshots are uploaded to LEO satellites. The payload switch does not have any route adaptation capabilities. All rerouting computations and decisions are made only by ground stations. The ground stations generate routes for each snapshot by determining k shortest paths between the source and the destination. Each one of the k paths is used for routing a specific type of traffic; e.g., delay sensitive traffic is routed on the first shortest path and other types of traffic are routed on the remaining k-1 paths. This scheme also does not consider traffic priority and does not support preemption.